1. Field of the Invention
This invention relates to low-density parity check decoding, and more particularly, to a low-density parity check decoder and decoding method which can save power.
2. Description of the Prior Art
Low-density parity check (LDPC) decoders use a linear error correcting code with parity bits. Parity bits provide a decoder with parity equations which can validate a received codeword. For example, a low-density parity check is a fixed length binary code wherein all the symbols added together will equal zero.
During encoding, all data bits are repeated and transmitted to encoders, wherein each encoder generates a parity symbol. Codewords are formed of k information digits and r check digits. If the length of the codeword is n then the information digits, k, will equal n−r. The codewords can be represented by a parity check matrix, which consists of r rows (representing equations) and n columns (representing digits), and is represented in FIG. 1. The codes are called low-density because the parity matrix will have very few ‘1’s in comparison to the number of ‘0’s. During decoding, each parity check is viewed as a single parity check code, and is then cross-checked with others. Decoding occurs at check nodes, and cross-checking occurs at variable nodes.
LDPC engines support three modes: hard decision hard decoding, soft decision hard decoding, and soft decision soft decoding. FIG. 1 illustrates the parity check matrix H and a Tanner graph, which is another way of representing the codewords, and is used to explain the operation of the LDPC decoder for hard decision soft decoding when using a bit flipping algorithm.
The check nodes, which are represented by the square boxes, are the number of parity bits; and the variable nodes, which are represented by the circular boxes, are the number of bits in a codeword. If a code symbol is involved in a particular equation, a line is drawn between the corresponding check node and variable node. ‘Messages’, which are estimates, are passed along the connecting lines, and combined in different ways at the nodes. Initially, the variable nodes will send an estimate to the check nodes on all connecting lines containing a bit believed to be correct. Each check node then takes all the other connected estimates, makes new estimates for each variable node based on this information, and passes the new estimate back to the variable nodes. The new estimate is based on the fact that the parity check equations force all variable nodes connected to a particular check node to sum to zero.
The variable nodes receive the new information and use a majority rule (a hard decision) to determine if the value of the original bit they sent was correct. If not, the original bit will be ‘flipped’. The bit is then sent back to the check nodes, and these steps are repeated for a predetermined number of iterations or until the parity check equations at the check nodes are satisfied. If these equations are satisfied (i.e. the value calculated by the check nodes matches the value received from the variable nodes) then Early Termination can be activated, which allows the system to exit the decoding process before the maximum number of iterations is reached.
The parity check constraints are performed by doing a syndrome check. A valid codeword will satisfy the equation H. CT=S=0, wherein H is the parity matrix, C is the hard decision codeword and S is the syndrome. When the syndrome equals zero, this means that no further information is required and the decoding process is complete. Typically, a hard decision and a syndrome check are performed during each iteration, wherein a non-zero syndrome means there is odd parity and a new decoding iteration is required.
Decoders have a power issue, wherein the more complicated they are, the more power they use. The above bit flipping algorithm can support both hard decision hard decoding and hard decision soft decoding modes. Hard decision hard decoding is the lowest power mode as it only involves 1 bit. As the number of error bits increases, however, the power issue starts to become more important. Above about 25 error bits, the throughput of the bit flipping algorithm starts to drop. Above about 40 error bits, it is better to switch to hard decision soft decoding, but the speed of the algorithm will be very unstable when a different mode is entered.